The present invention relates generally to data management and more particularly to methods and apparatus for managing data for rotated or skewed images.
The present invention is directed to applications having graphical objects that are sampled images, or slices of sampled images. A sampled image (or image) can be defined in a source space that includes sequentially ordered source samples arranged in source rows. Data management of the image may be complicated by the application of one or more transformations for transforming the source image into a different device space. For example, in a printer or other display device, it is often required to receive a sampled image from some source, store it in an intermediate data store (e.g., a computer""s random access memory or a file on a computer""s file system), and then render it using a transformation matrix into the device space of a raster device.
The sampled image can be defined in a source space which comprises a two-dimensional orthonormal coordinate system in which the samples of the sampled image form a square lattice. The x-axis in source space is oriented along the fast scan direction of the sampled image, that is, the direction of the typical linear ordering of sequential samples into rows. The y-axis in source space is oriented along the slow scan direction of the sampled image, that is, the direction of the typical linear ordering of sequential rows. In the printer example described above, the image data is often very large, and usually received by the data store in sequential source rows, which may be grouped into slices. A source row is a sequential row of samples in a sampled image, spanning the entire width of the sampled image. A slice is a group of sequential source rows.
The raster device can be defined in a device space which comprises a two-dimensional orthogonal coordinate system in which the raster elements of the raster device form a rectangular lattice. The x-axis in device space is oriented along the fast scan direction of the raster device, that is, the direction of the typical linear ordering of sequential raster elements into rasters (scan lines). The y-axis in device space is oriented along the slow scan direction of the raster device, that is, the direction of the typical linear ordering of sequential rows (scan lines) of rasters.
Rendering is a process for visually displaying a sampled image by converting it into raster elements on a raster device.
The conversion includes an affine coordinate transformation from source space into device space. The transformation may include many forms of xe2x80x9crotationxe2x80x9d including translation, scaling, shearing, as well as a conventional rotation, and combinations of these. An affine coordinate transformation is a geometric transformation of a coordinate system (as a translation, rotation, or a uniform stretching) that carries straight lines into straight lines and parallel lines into parallel lines, but may alter distances between points and angles between lines.
When source space and device space are not aligned, then the rendering of a sampled image from the source to the raster device results in a rotated image. A rotated image includes an affine coordinate transformation from source space into device space, such that the x-axis in source space is carried into device space with an orientation not parallel or aligned with the x-axis in device space. The transformation of the source image to device space may result in numerous data management issues.
Many raster devices are managed in bands. The data store required to support the raster elements of a typical four-color halftoned bi-level raster device at 1440 dpi resolution is almost a megabyte per square inch. Thus, to manage an entire A4-size page of raster data for such a device might require approximately a 90 MB data store, which is a prohibitive amount in many applications. However, to manage only a band at a time of raster data takes a much smaller data store; for example a band 512 scan lines high and the width of an A4 page, on the same device, would require approximately only a 3 MB data store.
Banded raster devices are implemented with a variety of techniques, which are fairly well known in the printer industry. Generally speaking during the render process, bands are rendered sequentially, then delivered to the raster device in order. But the graphical objects to be rendered onto the page are not necessarily received by the render engine in the same order as required for sequential band rendering. A display list can be used to store all graphical objects to be rendered onto the page, until it is certain that all objects to be rendered onto a specified band are stored. Then that band may be rendered. In this case, the data store (or image store) may be considered logically part of the display list, although it may be physically part of or separate from the data store used for the display list.
If a sampled image is rendered without rotation, that is with source rows parallel to raster device scan lines, then it is relatively easy to manage the image store incrementally. As each band is rendered, the source slices intersecting that band and not intersecting any other un-rendered bands may be discarded, freeing up a portion of the data store to receive new data.
When the sampled image is rotated, data management of the image data becomes much more difficult. For example, in the nominal worst case the image may be designated to be rotated ninety degrees, so that the source rows are rendered perpendicular to raster device scan lines. In this case, each slice of the source unrotated image intersects potentially many or all bands, and each affected band intersects all slices. There is no opportunity for incremental management of the data store, since as long as any of the image data must be stored, it all must be stored.
Another data management problem may arise when transporting image data from one data store to another. For example, in a distributed system, a process receiving a sampled image may be physically or logically separated from the rendering process. In this case, the image data must be transported from one process to the other, by sending the data over a communication channel, or by exchanging data pointers via a computer technique called inter-process communication (IPC). Regardless of the means of transport, it is often desirable to transport the image data incrementally, where the preferred increment is a band. Where, the image data associated with an output band spans a large number of the source rows associated with the sampled image, the incremental transport requires the maintenance of all of the data in the data store throughout the transport.
Data management can also affect the efficiency of a rendering process. On banded raster devices, image data is typically rendered a scan line at a time. The rendering operation requires sequentially accessing all the image samples intersected by the scan line. When the sampled image is not rotated, the sequential access generally approximates an access to a single source row, and has a high degree of locality of access. In an operation accessing multiple elements of data from a data store, the operation is said to have xe2x80x9clocality of accessxe2x80x9d if each element sequentially accessed is close to (or xe2x80x9clocal toxe2x80x9d) the previously accessed element. The definition of xe2x80x9cclose toxe2x80x9d depends on the physical characteristics of the data store, but generally operations with high degree of locality of access can occur more efficiently and more quickly than operations with a low degree of locality of access. This efficiency results from two common techniques for sequential data access, caching and burst (for computer memory) or buffered (for a file system) accesses. When the image is to be rotated in the rendering process, the xe2x80x9caccessxe2x80x9d spans many (or all) of the source rows resulting in a poor locality of access factor, which may impair the efficiency of the rendering operation.
In summary, sampled image data is typically ordered in sequences of source rows as described above. The ordering of data (defined in a source space), when the image is to be rotated (into a device space), is not conducive to (a) cutting the image into bands, (b) managing the image data in a band-oriented way, for incremental management of an image store or for incremental transport of image data, or (c) efficient sequential access, with a high degree of locality of access, by a rendering process. Thus, management and rendering of image data for rotated images may require a much larger data store, and be much less efficient, than for non-rotated images.
In one aspect, the invention provides a method of managing a source image that is output in a rotated or skewed orientation to a raster buffer. The source image includes a plurality of source samples arranged in source rows having a source direction. The raster buffer is oriented in a destination space and receives the rotated or skewed image as a series of samples in rows defined by a destination direction. The raster buffer provides rows of samples to a rendering device for rendering scan lines for output on a raster device. The method includes determining an angle between the source direction and the destination direction and adjusting the organization of the source samples to align source samples in scan rows where each scan line can be rendered from the raster buffer using at most a predetermined small number of scan rows.
Aspects of the invention can include one or more of the following features. The step of determining the angle includes determining if the angle measured in source space is between 0 and xe2x88x9245 degrees, and if not initially adjusting the organization of the samples so that the angle is between 0 and xe2x88x9245 degrees.
The step of initially adjusting includes determining if the angle or an effective new angle is between 45 and 135 degrees or xe2x88x92135 and xe2x88x9245 degrees, and, if so, revising the ordering of samples by transposing the samples relative to a line at 45 degrees passing through an origin of the source image resulting in an effective new angle falling between xe2x88x9245 and 45 degrees or 135 and 225 degrees.
The step of initially adjusting includes determining if the angle or an effective new angle is between 90 and 270 degrees, and, if so, reversing the x coordinate ordering of the samples resulting in an effective new angle falling between 90 and xe2x88x9290 degrees.
The step of initially adjusting includes determining if the angle or an effective new angle is between 0 and 180 degrees, and, if so, reversing the y coordinate ordering of the samples resulting in an effective new angle falling between 0 and xe2x88x92180 degrees.
The step of initially adjusting includes processes selected from the group of transposing in both axes, reversing the ordering in the x-axis and reversing the ordering in the y-axis for samples depending on the slope.
The method can include locating one or more marking lines that span a width of the source image. The marking lines are parallel to the rows in the raster buffer and have a slope defined by the angle. Transition points along the length of a marking line are identified. Each transition point defines a last source sample in a current source row that the marking line passes through prior to transitioning to a next source row of source samples. The step of adjusting includes shifting columns of source samples enclosed between transition points to align the source samples in scan rows.
The marking line is a idealized scan line. Only one marking line is located spanning the width of the source image and enclosed within the boundaries of the source image. Only one marking line is located that extends beyond the boundaries of the source image and spans the entire width of the source image.
The step of adjusting the organization of the source samples is combined with other image processing steps selected from the group of compression, decompression, resampling and color correction to achieve computational efficiency compared to doing such steps in a sequence.
The method includes locating one or more marking lines spanning a width of the source image, identifying transition points along a width of the source image where the transition points define a point where adjacent source samples in a source row map to different marking lines and wherein the step of adjusting includes shifting columns of source samples enclosed between transition points to align the source samples in scan rows.
Each sample is mapped to exactly one marking line. The columns are incrementally shifted one unit at each transition point. The incremental shifts are accumulated across a width of the sampled image.
One unit is equal to one row or one block. A block is sized to achieve byte alignment when adjusting samples. The predetermined small number of scan rows is three.
The method includes locating a plurality of marking lines spanning a width of the source image and the step of adjusting includes associating each source sample with a single marking line and adjusting the order of the samples including assigning all source samples associated with each marking line to a unique scan row. A source sample is associated with a marking line that intersects the source sample. The step of associating includes determining if a source sample is intersected by two or more marking lines associated with two or more scan rows and if so, assigning the source sample to a first scan row that is to be rendered of the two or more scan rows.
All source rows of the source image are available for processing and the step of adjusting outputs data to the rendering device a scan row at a time. The step of adjusting identifies all source samples associated with a scan row and outputs all those source samples in order as a scan row to the rendering device. The scan rows are stored in a memory device and the source rows are received and processed a slice at a time. A slice includes a set of source rows. Each source row is processed including determining which scan row to assign each source sample and storing the source sample in the assigned scan row in the memory device.
The source samples are not byte aligned. The method further includes grouping source samples in blocks that are aligned with a byte boundary and the step of adjusting the ordering of samples adjusts groups of samples on block boundaries. The step of adjusting includes determining a horizontal block width defining a number of consecutive samples grouped together in a block of samples to achieve byte boundary alignment, and determining a vertical block height defining a number of consecutive horizontal samples in consecutive rows to be grouped together in each block of samples. The vertical block height is determined using the angle and the horizontal block width.
In another aspect the invention provides a method of managing data for a source image to be printed in a rotated or skewed orientation on an printing device. The source image includes a plurality of source samples arranged in source rows having a source direction. The printing device prints a rotated source image in a series of scan lines defined by a scan direction. The method includes determining an angle between the source direction and the scan direction and locating an idealized scan line that spans a width of the source image. The idealized scan line is parallel to the scan lines of the printing device and has a slope defined by the angle. The method includes identifying transition points along the length of the idealized scan line where each transition point defines a last sample in a source row touched by the idealized scan line. The organization of the source samples is adjusted including shifting columns of source samples enclosed between transition points to align the source samples in scan rows. Consecutive scan rows are outputted incrementally to the printing device to support rendering of source samples for each scan line.
In another aspect the invention provides a method of managing a source image that is transferred in a rotated or skewed orientation to an output buffer. The source image includes a plurality of source samples arranged in source rows having a source direction. The output buffer is oriented in a destination space and receives the rotated or skewed image as a series of samples in destination rows defined by a destination direction. The output buffer outputs the rotated or skewed image in an output order to another device. The method includes determining an angle between the source direction and the destination direction and adjusting the organization of the source samples to align source samples in scan rows to reflect the output ordering of the output buffer.
In another aspect, the invention provides a method of incrementally managing image data that is output in a rotated or skewed orientation to a raster buffer. The image data includes a plurality of source samples arranged in source rows having a source direction. The raster buffer is oriented in a destination space and receives the rotated or skewed image data as a series of samples in destination rows defined by a destination direction. The method includes determining an angle between the source direction and the destination direction, adjusting the organization of the source samples to align source samples in scan rows to reflect a render ordering of destination rows of the raster buffer, storing the reorganized samples in a intermediary data store and incrementally transferring a set of scan rows at a time to a rendering device for rendering and deleting a transferred set from the intermediary data store.
In another aspect the invention provides a method for minimizing the number of samples provided to a rendering engine in order to render a rotated or skewed image and includes receiving a sampled image defined in a source space. The sampled image includes a plurality of source samples arranged in source rows having a source direction. A destination region intersecting a portion of the sampled image is identified. The destination region is oriented in a destination space reflecting a render ordering of a rotated or skewed transformation of the sampled image to the destination space. A subset of the samples of the sampled image are selected that are enclosed by the destination region, the selected subset of samples are arranged into scan rows and the rows of samples associated with the destination region are provided to the render engine in scan row order.
In another aspect the invention provides a method of managing data for a source image to be printed in a rotated or skewed orientation on an printing device. The source image includes a plurality of source samples arranged in source rows having a source direction. The printing device prints a rotated source image in a series of scan lines defined by a scan direction. The method includes adjusting the organization of the source samples including shifting columns of source samples align the source samples in scan rows that and incrementally outputting consecutive scan rows to the printing device to support rendering of source samples for each scan line. Scan lines are rendered into a raster buffer producing raster data from the samples in the scan rows. Thereafter the scan lines are printed.
Features of the invention can include one or more of the following advantages. The data in a rotated sampled image can be re-ordered to make the order of samples in an image store more closely approximate the order of samples intersected by raster device scan lines. This improves xe2x80x9clocality of accessxe2x80x9d to the data. As a result, it becomes possible to efficiently cut the image data into bands, manage the image store incrementally, transport image data incrementally, and render the rotated image more efficiently.
The invention provides a process for efficiently re-ordering rotated image data to be arranged into sequences of scan rows. The samples in each scan row approximate the set of samples needed to render a particular raster device scan line, or a subset thereof. Sets of sequential reordered scan rows contain all the samples needed to render a particular band. The image data needed to render a given band may therefore be selected by selecting the corresponding set of sequential reordered scan rows.
The re-ordering does not change the number of samples in the image, nor the values of any of those samples. Thus, there is no degradation of the image compared to other image data management techniques, and no expansion of the data.
Some overlap is necessary when selecting a band; i.e., at the boundary between successive bands, some rotated image scan rows contain samples intersecting both bands. However, the maximum size of that overlap is a small constant number of rotated image scan rows, depending on the variant of the re-ordering process used. Thus, the selecting of bands is reliable, and the data expansion when transporting the data in bands is small and known in advance.
The re-ordered image data may be accessed by a rendering process in a way fundamentally similar to accessing non-re-ordered data. Thus, this invention is easily integrated with existing techniques for rendering rotated images as well as with other image data management techniques, including compression and re-sampling.
Sampled images received in slices may be re-ordered slice-by-slice into multiple data stores, or multiple slices may be re-ordered into a combined data store. The former may be more convenient; the latter decreases the number of subsets of image data to be managed and subsequently rendered.
Other features and advantages of the invention will become apparent from the following description, including the drawings and claims.